/**
10
1 2 2 1 3 3 1 4 4 1
-> ans = 3, 先 2 后 4 再 3
9
1 1 2 2 1 3 3 1 1
-> ans = 3, 先 2 后 3 再 1
8
1 2 2 1 1 3 3 1
-> ans = 4, 先 2 后 3 再 1 1
7
1 2 2 1 3 3 1
-> ans = 2, 先 2 后 3
*/
#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

const int inf = INT_MAX / 2;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i ++) cin >> a[i];
  vector<int> color(1), cnt(1);
  for (int i = 1; i <= n; i ++) {
    if (i == 1 || a[i] != a[i - 1]) {
      color.push_back(a[i]);
      cnt.push_back(1);
    } else {
      cnt.back() ++;
    }
  }
  n = color.size() - 1;
  vector<vector<int>> dp(n + 1, vector<int>(n + 1));
  vector<vector<array<int, 4>>> f(n + 1, vector<array<int, 4>>(n + 1, {inf, inf, inf, inf}));
  for (int l = n; l >= 1; l --) {
    f[l][l][cnt[l] != 1] = 0;
    dp[l][l] = max(1, 3 - cnt[l]);
    for (int r = l + 1; r <= n; r ++) {
      dp[l][r] = inf;
      for (int k = l; k < r; k ++) {
        dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
      }
      if (color[l] == color[r]) {
        for (int k = l; k < r; k ++) {
          if (color[k] == color[l]) {
            for (int c = 0; c <= 2; c ++) {
              if (cnt[r] == 1) {
                f[l][r][c + 1] = min(f[l][r][c + 1], f[l][k][c] + dp[k + 1][r - 1]);
              } else if (c != 2) {
                f[l][r][3] = min(f[l][r][3], f[l][k][c] + dp[k + 1][r - 1]);
              }
            }
          }
        }
        for (int c = 0; c <= 3; c ++) {
          dp[l][r] = min(dp[l][r], f[l][r][c] + max(2 - c , 0));
        }
      }
    }
  }
  cout << dp[1][n] << endl;
}